package algorithms.leecode;

import java.util.HashMap;
import java.util.Map;

public class Au70 {
    public static void main(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        System.err.println(new Au70().calculate(0,44,map));
    }
    public int calculate(int curr, int n, Map<Integer,Integer> map) {
        if (n == 2) {
            return 2;
        }
        if (curr == n) {
            return 1;
        }
        if (map.containsKey(curr)) {
            return map.get(curr);
        }
        if (curr > n) {
            return 0;
        }
        int x = calculate(curr + 1,n,map);
        if (x != 0) {
            map.put(curr + 1,x);
        }
        int y = calculate(curr + 2,n,map);
        if (y != 0) {
            map.put(curr + 2,y);
        }
        return x + y;
    }
}
